home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 6717 < prev    next >
Encoding:
Text File  |  1996-08-05  |  2.9 KB  |  86 lines

  1. Path: newsxfer2.itd.umich.edu!caen!usenet
  2. From: Chris Peikert <cpeikert@kamsc.seds.org>
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Tough FACTORIAL math problem...
  5. Date: Sun, 18 Feb 1996 21:54:02 -0500
  6. Organization: Kalamazoo Area Math & Science Center
  7. Message-ID: <3127E64A.6A4F@kamsc.seds.org>
  8. References: <4fr8be$ass@news.iconn.net> <4g898j$5t@umbc9.umbc.edu>
  9. NNTP-Posting-Host: @pm137-13.dialip.mich.net
  10. Mime-Version: 1.0
  11. Content-Type: text/plain; charset=us-ascii
  12. Content-Transfer-Encoding: 7bit
  13. X-Mailer: Mozilla 2.0 (Win95; I)
  14.  
  15. Jonas J. Schlein wrote:
  16. > In article <4fr8be$ass@news.iconn.net>, The Crow <thecrow@iconn.net> wrote:
  17. > |> Here is what I am trying to do, I want to find the last NON-ZERO digit of a
  18. > |> given factorial.  For instance,
  19. > |>
  20. > |> 5! = 120
  21. > |>
  22. > |> so the last non-zero digit is 2.  I want to be able to do this up to 1000.
  23. > |> Problem is, no matter how huge of a data-type you use, there isn't any way
  24. > |> for the computer to handle 1000!, it is however possible to find the last
  25. > |> non-zero digit somehow.  One thing I have tried is as I went through
  26. > |> mulitplying the series of numbers in the factorial (5 * 4 * 3 * 2) I would
  27. > |> remove all the trailing ZEROS, I got this to work up to 789, but it wont
  28. > |> work with 1000 and i am not really sure why.  If anyone has a clue how I
  29. > |> can do this let me know.
  30.  
  31. Funny, this is the exact problem #1 and test case on the USACO 
  32. qualifying round.  Seeing as how it's past the deadline for writing the 
  33. programs, here's how I did it:
  34.  
  35. ---CODE STARTS HERE---
  36. #include <iostream.h>
  37.  
  38. int rtDigit(int n) {
  39.  long dig=1;
  40.  for(int i=2; i<=n; i++) { // computing factorial
  41.   dig *= i;
  42.   while(!(dig % 10))       // chop of righthand 0s
  43.    dig /= 10;
  44.   dig %= 1000;             // keep last three nonzero digits
  45.  }
  46.  return (dig % 10);        // return last digit
  47. }
  48.  
  49.  
  50. void main() {
  51.  int n=1;
  52.  while(n) {                // input != 0
  53.   cout << "Input:\n";
  54.   cin >> n;
  55.   if(n) {
  56.    cout << "Output:\n";
  57.    cout << rtDigit(n) << "\n";  // return the digit
  58.   }
  59.  }
  60. }
  61. ---CODE ENDS HERE---
  62.  
  63. The critical code portion is this:
  64.  
  65.   dig *= i;
  66.   while(!(dig % 10))       // chop of righthand 0s
  67.    dig /= 10;
  68.   dig %= 1000;             // keep last three nonzero digits
  69.  
  70. in the for loop.  It kills all of the righthand 0s, then keeps only the 
  71. three righthand non-zero digits.  Worst-case scenario involves 
  72. multiplication of 999*999, which is safe for a long.  The reason I kept 
  73. the last _three_ nonzero digits is because the thousands digit of "dig" 
  74. cannot possibly contribute anything to the rightmost nonzero digit if n 
  75. is less than 1000.  That, and it works that way :).
  76.  
  77. But I must ask that, upon presenting the problem, you mention that it's 
  78. for a contest.  Otherwise, people who know will think you're cheating.
  79.  
  80. ----------------------------------------
  81. Of all the people I know,
  82. you're one of them.
  83. Chris Peikert cpeikert@kamsc.seds.org
  84. http://www.kamsc.k12.mi.us/sp96/cpeikert
  85.